#include <bits/stdc++.h>
#define ll long long
using namespace std;

inline ll read(){
    ll x=0;char c=getchar();
    while (!isdigit(c))c=getchar();
    while (isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x;
}

ll a[200005],dp[200005],to[200005],tag;
multiset<ll,greater<ll>> ms;

inline void add(ll x){
    tag+=x;
}

inline ll querymax(){
    return (*ms.begin())+tag;
}

inline ll querypoint(ll x){
    return dp[x]+tag;
}

inline void upd(ll x,ll v){
    ms.erase(ms.find(dp[x]));
    dp[x]=v-tag;
    ms.insert(dp[x]);
}

int main(){
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(false);
    ll t;
    cin >> t;
    while (t--){
        ll n;
        cin >> n;
        for (ll i=0;i<=n+1;i++){
            a[i]=0;
        }
        vector<ll> book;
        for (ll i=1;i<=n;i++){
            cin >> a[i];
            book.push_back(a[i]);
        }
        book.push_back(0);
        sort(book.begin(),book.end());
        for (ll i=0;i<book.size();i++)to[i]=book[i];
        for (ll i=1;i<=n;i++){
            a[i]=lower_bound(book.begin(),book.end(),a[i])-book.begin();
        }
        dp[0]=0;
        for (ll i=1;i<book.size();i++)dp[i]=-1e12;
        ms.clear();
        tag=0;
        for (ll i=0;i<book.size();i++)ms.insert(dp[i]);
        for (ll i=1;i<=n;i++){
            if (a[i]==a[i-1])add(to[a[i]]);
            ll z=max(querymax(),querypoint(a[i])+(a[i]==a[i-1]?0:to[a[i]]));
            upd(a[i-1],z);

        }
        ll ans=0;
        for (ll i=0;i<book.size();i++){
            ans=max(ans,querypoint(i));
        }
        cout<< ans<<"\n";
    }
    return 0;
}
